﻿public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)//构造函数
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution94
{
    //递归法
    public IList<int> InorderTraversal1(TreeNode root)
    {

        IList<int> res = new List<int>();

        //先序遍历中左右
        Bianli(root, res);
        return res;


    }

    public void Bianli(TreeNode root, IList<int> res)
    {
        if (root == null)
        {
            return;
        }
        Console.WriteLine("当前节点：" + root.val);
        res.Add(root.val);
        Bianli(root.left, res);
        Bianli(root.right, res);
        //递归的终止条件
    }

    //迭代法
    public IList<int> InorderTraversal(TreeNode root)
    {

        IList<int> res = new List<int>();

        //先序遍历中左右

        Stack<TreeNode> q=new Stack<TreeNode> ();
        if (root == null)
        {
            return res;
        }
        TreeNode node = root;
        while (node!=null|q!=null)//q为空
        {

            while(node!=null)//找到最左下角
            {
                //入栈的同时也加入数组
                q.Push(node);
                res.Add(node.val);
                node = node.left;
            }
            node = q.Pop();//返回父亲节点
            node = node.right;//开始遍历右边的
        }


        return res;


    }


}
class Program94
{

    static void Main94(string[] args)
    {

        // 创建二叉树示例
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        // 创建 Solution 实例并调用 InorderTraversal 方法
        Solution94 solution = new Solution94();
        IList<int> result = solution.InorderTraversal(root);
        // 打印遍历结果
        Console.WriteLine("中序遍历结果：");
        foreach (int num in result)
        {
            Console.WriteLine(num);
        }
    }

}